package swordoffer.offer40;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueSolution {
    /**
     * 优先队列解法
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        int len = input.length;
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || len == 0 || k == 0 || k > len) {
            return res;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        for (int i = 0; i < len; i++) {
            if (maxHeap.size() < k) {
                maxHeap.offer(input[i]);
            } else if (input[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(maxHeap.poll());
        }
        return res;
    }
}
